---
title: "6、数字接龙"
created: 2025-11-28
tags:
  - 算法
---

# 6、数字接龙

## 题目 数字接龙

![[image-52aa9292.png]]

## 思路分析

就是这题陷进去了 浪费了一个多小时

一开始说这道题有问题 然后我先写了第七题 回过头来才看的这题 早知道也看一眼最后一题了

我一直找不到bug在哪里 导致答案一直输出-1 ……

然后就不服气了 因为思路都没什么问题 一想到自己写半天和别人直接输出-1是一样的分就气 然后一直改 导致最后一题看都没看 因为不确定最后一题能写出来
万一写不出 这题呼之欲出了又没拿到 就亏大了

结果就是 在两题选一题拿分的情况下 选择了两题都不拿分hh

回到寝室一眼就看出来了问题……

所以懊悔不已 要是出去上个厕所 转变一下思路 说不定两题都能写出来 70分省一前几名都有了 可惜可惜

## 代码实现

```cpp
 /*

左上角00出发 到n-1,n-1 但不是线性dp的模型

可以往8个方向走 可以借鉴经验 一定不会往上和左上 和左走

意味着 可以往 右上 右 右下 下 左下 5个方向走

还得有个要求 走过的路 上面的数要是012…k-1的循环

每个格子只能走一次 且不能交叉路径

后面两个限制貌似可以用前面的分析抵消

要求找到路径 和 回溯

应该是bfs dfs 数据范围也正常 10 没跑了

整理一下 从起点 0，0 走到 终点n-1,n-1

每个点可以往5个方向拓展 右上 右 右下 下 左下

要求字典序最小 那就是这个拓展顺序 无需改变

 拓展的时候 要另外加一个判断 要是上一个数+1 若上一个数为k-1 则该数为0 可能要传入一个last变量

*/

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=15;

int n,k;

int g[N][N];

bool st[N][N];

int path[N];

bool success=false;

int dx[5]={-1,0,1,1,1};

int dy[5]={1,1,1,0,-1};

int p[5]={1,2,3,4,5};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=n-1 && !st[x][y];

}

//void print_path(int x,int y){

//	if(x==0 && y==0)

//		return;

//	if(pre[x][y]==1)//这个点由上个点往右上走来 往左下找回上个点

//		print_path(x+1,y-1);

//	if(pre[x][y]==2)

//		print_path(x,y-1);

//	if(pre[x][y]==3)

//		print_path(x-1,y-1);

//	if(pre[x][y]==4)

//		print_path(x-1,y);

//	if(pre[x][y]==5)

//		print_path(x-1,y+1);

//	cout<<pre[x][y];

//}

bool check(int ux,int uy,int nx,int ny){

	if(g[ux][uy]==k-1){

		if(g[nx][ny]==0)

			return true;

	}

	else{

		if(g[nx][ny]==g[ux][uy]+1)

			return true;

	}

	return false;

}

void dfs(int x,int y,int u){

	if(u==n*n-1){

		for(int i=0;i<n*n-1;i++){

			cout<<path[i];

		}

		success=true;

		return;

	}

	for(int i=0;i<5;i++){

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny) && check(x,y,nx,ny)){

			st[nx][ny]=true;

			path[u]=p[i];

			dfs(nx,ny,u+1);

			st[nx][ny]=false;

			path[u]=-1;

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	//题目说读n行 又给了空格 鬼知道是不是g[i][j]一个一个读入 万一只读3次就寄了

	//按行处理 防恶心

	string s;

	getline(cin,s);

	for(int i=0;i<n;i++){

		getline(cin,s);

		for(int k=0,j=0;k<s.size();k++){

			if(s[k]!=' ')

				g[i][j++]=s[k]-'0';

		}

	}

//	for(int i=0;i<n;i++){

//		for(int j=0;j<n;j++){

//			cout<<g[i][j]<<" ";

//		}

//		cout<<endl;

//	}

	dfs(0,0,0);

	if(!success)

		cout<<"-1";

	return 0;

 }
```

## 同类题型

## 视频讲解

---
⬅️ [[5、宝石组合|5、宝石组合]] 🏠 [[00-刷题理模型]] ➡️ [[7、爬山|7、爬山]]